Predicting bounce rates in sponsored search advertisements.
This paper explores an important and relatively unstudied quality measure of a sponsored search advertisement: bounce rate. The bounce rate of an ad can be informally defined as the fraction of users who click on the ad but almost immediately move on to other tasks. A high bounce rate can lead to poor advertiser return on investment, and suggests search engine users may be having a poor experience following the click. In this paper, we first provide quantitative analysis showing that bounce rate is an effective measure of user satisfaction. We then address the question, can we predict bounce rate by analyzing the features of the advertisement? An affirmative answer would allow advertisers and search engines to predict the effectiveness and quality of advertisements before they are shown. We propose solutions to this problem involving large-scale learning methods that leverage features drawn from ad creatives in addition
PLANET Massively Parallel Learning of Tree Ensembles with MapReduce.
Classification and regression tree learning on massive datasets is a common data mining task at Google, yet many state of the art tree learning algorithms require training data to reside in memory on a single machine. While more scalable implementations of tree learning have been proposed, they typically require specialized parallel computing architectures. In contrast, the majority of Google’s computing infrastructure is based on commodity hardware. In this paper, we describe PLANET: a scalable distributed framework for learning tree models over large datasets. PLA-NET defines tree learning as a series of distributed computations, and implements each one using the MapReduce model of distributed computation. We show how this framework supports scalable construction of classification and regression trees, as well as ensembles of such models. We discuss the benefits and challenges of using a MapReduce compute cluster for tree learning, and demonstrate the scalability of this approach by applying it to a real world learning task from the domain of computational advertising. 1.
Privacy%2Dpreserving indexing of documents on the network.
We address the problem of providing privacypreserving  search over distributed accesscontrolled  content. Indexed documents can  be easily reconstructed from conventional (inverted)  indexes used in search. The need to  avoid breaches of access-control through the  index requires the index hosting site to be  fully secured and trusted by by all participating  content providers. This level of trust is  impractical in the increasingly common case  where multiple competing organizations or individuals  wish to selectively share content. We  propose a solution that eliminates the need of  such a trusted authority. The solution builds  a centralized privacy-preserving index in conjunction  with a distributed access-control enforcing   search protocol. The new index provides  strong and quantifiable privacy guarantees  that hold even if the entire index is made  public. Experiments on a real-life dataset validate  performance of the scheme. The appeal  of our solution is two-fold: (a) Content  providers maintain complete control in defining  access groups and ensuring its compliance,  and (b) System implementors retain tunable  knobs to balance privacy and e#ciency concerns  for their particular domains.
Scaling up all pairs similarity search.
Pairs of similar records with their similarity score (Similarity Graph)
Introduction to special issue ACM SIGKDD 2006.

Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

Data Privacy through Optimal k%2DAnonymization.
Data de-identification reconciles the demand for release of data for research purposes and the demand for privacy from individuals. This paper proposes and evaluates an optimization algorithm for the powerful de-identification procedure known as k-anonymization. A k-anonymized dataset has the property that each record is indistinguishable from at least k – 1 others. Even simple restrictions of optimized k-anonymity are NP-hard, leading to significant computational challenges. We present a new approach to exploring the space of possible anonymizations that tames the combinatorics of the problem, and develop data-management strategies to reduce reliance on expensive operations such as sorting. Through experiments on real census data, we show the resulting algorithm can find optimal k-anonymizations under two representative cost measures and a wide range of k. We also show that the algorithm can produce good anonymizations in circumstances where the input data or input parameters preclude finding an optimal solution in reasonable time. Finally, we use the algorithm to explore the effects of different coding approaches and problem variations on anonymization quality and performance. To our knowledge, this is the first result demonstrating optimal k-anonymization of a nontrivial dataset under a general model of the problem. 1.
Exploiting the web for point%2Din%2Dtime file sharing.

FIMI %2704
For a transaction database, a frequent itemset is an itemset included in at least a specified number of transactions. To find all the frequent itemsets, the heaviest task is the computation of frequency of each candidate itemset. In the previous studies, there are roughly three data structures and algorithms for the computation: bitmap, prefix tree, and array lists. Each of these has its own advantage and disadvantage with respect to the density of the input database. In this paper, we propose an efficient way to combine these three data structures so that in any case the combination gives the best performance. 1.
The Hows%2C Whys%2C and Whens of Constraints in Itemset and Rule Discovery.

Auditing Compliance with a Hippocratic Database.
We introduce an auditing framework for determining whether a database system is adhering to its data disclosure policies. Users formulate audit expressions to specify the (sensitive) data subject to disclosure review. An audit component accepts audit expressions and returns all queries (deemed “suspicious”) that accessed the specified data during their execution. The overhead of our approach on query processing is small, involving primarily the logging of each query string along with other minor annotations. Database triggers are used to capture updates in a backlog database. At the time of audit, a static analysis phase selects a subset of logged queries for further analysis. These queries are combined and transformed into an SQL audit query, which when run against the backlog database, identifies the suspicious queries efficiently and precisely. We describe the algorithms and data structures used in a DB2-based implementation of this framework. Experimental results reinforce our design choices and show the practicality of the approach. 1
An evaluation of binary XML encoding optimizations for fast stream based xml processing.
This paper provides an objective evaluation of the performance impacts of binary XML encodings, using a fast stream-based XQuery processor as our representative application. Instead of proposing one binary format and comparing it against standard XML parsers, we investigate the individual effects of several binary encoding techniques that are shared by many proposals. Our goal is to provide a deeper understanding of the performance impacts of binary XML encodings in order to clarify the ongoing and often contentious debate over their merits, particularly in the domain of high performance XML stream processing.
Privacy%2DPreserving Indexing of Documents on the Network.
We address the problem of providing privacypreserving  search over distributed accesscontrolled  content. Indexed documents can  be easily reconstructed from conventional (inverted)  indexes used in search. The need to  avoid breaches of access-control through the  index requires the index hosting site to be  fully secured and trusted by by all participating  content providers. This level of trust is  impractical in the increasingly common case  where multiple competing organizations or individuals  wish to selectively share content. We  propose a solution that eliminates the need of  such a trusted authority. The solution builds  a centralized privacy-preserving index in conjunction  with a distributed access-control enforcing   search protocol. The new index provides  strong and quantifiable privacy guarantees  that hold even if the entire index is made  public. Experiments on a real-life dataset validate  performance of the scheme. The appeal  of our solution is two-fold: (a) Content  providers maintain complete control in defining  access groups and ensuring its compliance,  and (b) System implementors retain tunable  knobs to balance privacy and e#ciency concerns  for their particular domains.
Privacy%2DPreserving Indexing of Documents on the Network.
We address the problem of providing privacypreserving  search over distributed accesscontrolled  content. Indexed documents can  be easily reconstructed from conventional (inverted)  indexes used in search. The need to  avoid breaches of access-control through the  index requires the index hosting site to be  fully secured and trusted by by all participating  content providers. This level of trust is  impractical in the increasingly common case  where multiple competing organizations or individuals  wish to selectively share content. We  propose a solution that eliminates the need of  such a trusted authority. The solution builds  a centralized privacy-preserving index in conjunction  with a distributed access-control enforcing   search protocol. The new index provides  strong and quantifiable privacy guarantees  that hold even if the entire index is made  public. Experiments on a real-life dataset validate  performance of the scheme. The appeal  of our solution is two-fold: (a) Content  providers maintain complete control in defining  access groups and ensuring its compliance,  and (b) System implementors retain tunable  knobs to balance privacy and e#ciency concerns  for their particular domains.


Peer%2Dto%2DPeer Sharing of Web Applications.

Technological Solutions for Protecting Privacy.

YouServ a web%2Dhosting and content sharing tool for the masses.
YouServ is a system that allows its users to pool existing desktop computing resources for high availability web hosting and file sharing. By exploiting standard web and internet protocols (e.g. HTTP and DNS), YouServ does not require those who access YouServ-published content to install special purpose software. Because it requires minimal server-side resources and administration, YouServ can be provided at a very low cost. We describe the design, implementation, and a successful intranet deployment of the YouServ system, and compare it with several alternatives.
Vinci a service%2Doriented architecture for rapid development of Web applications.
Vinci is a local area service-oriented architecture designed for rapid development and management of robust web applications. Based on XML document exchange, Vinci is designed to complement and interoperate with wide area service-oriented architectures such as E-Speak and .NET. This paper presents the Vinci architecture, the rationale behind its design, and an evaluation of its performance. Specifically, we show how systems architected with Vinci are developed quickly, scaled effortlessly, and easily moved from prototype to production.


Report on the Workshop on Research Issues in Data Mining and Knowledge Discovery Workshop %28DMKD 2001%29.

Counting Models Using Connected Components.
Recent work by Birnbaum &amp; Lozinskii [1999] demonstrated  that a clever yet simple extension of the well-known DavisPutnam  procedure for solving instances of propositional  satisfiability yields an efficient scheme for counting the  number of satisfying assignments (models). We present a new  extension, based on recursively identifying connected  constraint-graph components, that substantially improves  counting performance on random 3-SAT instances as well as  benchmark instances from the SATLIB and Beijing suites. In  addition, from a structure-based perspective of worst-case  complexity, while polynomial time satisfiability checking is  known to require only a backtrack search algorithm enhanced  with nogood learning, we show that polynomial time  counting using backtrack search requires an additional  enhancement: good learning.  Introduction  Many practical problems from a variety of domains, most notably planning [Kautz &amp; Selman 1996], have been efficiently solved by formulating ...
Athena Mining%2DBased Interactive Management of Text Database.
Abstract. We describe Athena: a system for creating, exploiting, and maintaining a hierarchy of textual documents through interactive miningbased operations. Requirements of any such system include speed and minimal end-user e ort. Athena satis es these requirements through linear-time classi cation and clustering engines which are applied interactively to speed the development of accurate models. Naive Bayes classi ers are recognized to be among the best for classifying text. We show that our specialization of the Naive Bayes classi er is considerably more accurate (7 to 29 % absolute increase in accuracy) than a standard implementation. Our enhancements include using Lidstone&#039;s law of succession instead of Laplace&#039;s law, under-weighting long documents, and over-weighting author and subject. We also present a new interactive clustering algorithm, C-Evolve, for topic discovery. C-Evolve rst nds highly accurate cluster digests (partial clusters), gets user feedback to merge and correct these digests, and then uses the classi cation algorithm to complete the partitioning of the data. By allowing this interactivity in the clustering process, C-Evolve achieves considerably higher clustering accuracy (10 to 20 % absolute increase in our experiments) than the popular K-Means and agglomerative clustering methods. 1
Constraint%2DBased Rule Mining in Large%2C Dense Databases.
Constraint-based rule miners find all rules in a given dataset meeting user-specified constraints such as minimum support and confidence. We describe a new algorithm that directly exploits all user-specified constraints including minimum support, minimum confidence, and a new constraint that ensures every mined rule offers a predictive advantage over any of its simplifications. Our algorithm maintains efficiency even at low supports on data that is dense (e.g. relational data). Previous approaches such as Apriori and its variants exploit only the minimum support constraint, and as a result are ineffective on dense data due to a combinatorial explosion of “frequent itemsets”. 1.
Constraint%2DBased Rule Mining in Large%2C Dense Databases.
Constraint-based rule miners find all rules in a given dataset meeting user-specified constraints such as minimum support and confidence. We describe a new algorithm that directly exploits all user-specified constraints including minimum support, minimum confidence, and a new constraint that ensures every mined rule offers a predictive advantage over any of its simplifications. Our algorithm maintains efficiency even at low supports on data that is dense (e.g. relational data). Previous approaches such as Apriori and its variants exploit only the minimum support constraint, and as a result are ineffective on dense data due to a combinatorial explosion of “frequent itemsets”. 1.
Mining the Most Interesting Rules.
Several algorithms have been proposed for finding the “best, ” “optimal,” or “most interesting ” rule(s) in a database according to a variety of metrics including confidence, support, gain, chi-squared value, gini, entropy gain, laplace, lift, and conviction. In this paper, we show that the best rule according to any of these metrics must reside along a support/confidence border. Further, in the case of conjunctive rule mining within categorical data, the number of rules along this border is conveniently small, and can be mined efficiently from a variety of real-world data-sets. We also show how this concept can be generalized to mine all rules that are best according to any of these criteria with respect to an arbitrary subset of the population of interest. We argue that by returning a broader set of rules than previous algorithms, our techniques allow for improved insight into the data and support more user-interaction in the optimized rule-mining process. 1.
Efficiently Mining Long Patterns from Databases.
We present a pattern-mining algorithm that scales roughly linearly in the number of maximal patterns embedded in a database irrespective of the length of the longest pattern. In comparison, previous algorithms based on Apriori scale exponentially with longest pattern length. Experiments on real data show that when the patterns are long, our algorithm is more efficient by an order of magnimaximal frequent itemset, Max-Miner’s output implicitly and concisely represents all frequent itemsets. Max-Miner is shown to result in two or more orders of magnitude in performance improvements over Apriori on some data-sets. On other data-sets where the patterns are not so long, the gains are more modest. In practice, Max-Miner is demonstrated to run in time that is roughly linear in the number of maximal frequent itemsets and the size of the database, irrespective of the size of the longest frequent itemset. tude or more. 1.
Using CSP Look%2DBack Techniques to Solve Real%2DWorld SAT Instances.
We report on the performance of an enhanced version of the “Davis-Putnam ” (DP) proof procedure for propositional satisfiability (SAT) on large instances derived from realworld problems in planning, scheduling, and circuit diagnosis and synthesis. Our results show that incorporating CSP lookback techniques-- especially the relatively new technique of relevance-bounded learning-- renders easy many problems which otherwise are beyond DP’s reach. Frequently they make DP, a systematic algorithm, perform as well or better than stochastic SAT algorithms such as GSAT or WSAT. We recommend that such techniques be included as options in implementations of DP, just as they are in systematic algorithms for the more general constraint satisfaction problem.
Query Evaluation as Constraint Search%3B An Overview of Early Results.

Brute%2DForce Mining of High%2DConfidence Classification Rules.
This paper investigates a brute-force technique for mining classification rules from large data sets. We employ an association rule miner enhanced with new prun ing strategies to control combinatorial explosion in the number of candidates counted with each database pass. The approach effectively and efficiently extracts high confidence classification rules that apply to most if not all of the data in several classification benchmarks.  Introduction  Several data mining tasks require dividing up the entities of a database into various classes. Junk-mailers are wellknown users of classification technology, using it to avoid sending out flyers to persons unlikely to be interested in the product being promoted. The task requires a classifier that  is usually automatically generated from a &#034;training database &#034; of pre-classified entities. Several approaches have appeared in the AI, statistics, and data-mining literature, and some methods made to scale to large data sets [Shafer et al. 96]. B...
InfoSleuth Semantic Integration of Information in Open and Dynamic Environments %28Experience Paper%29.

The InfoSleuth Project.
InfoSleuth is a research project at MCC that is developing and deploying new technologies for finding information available both in corporate networks and in external networks, such as networks based on the emerging National Information Infrastructure (NII). The InfoSleuth research is based on the Carnot technology that has been developed at MCC over the last 4 years. Carnot has been successfully used to integrate heterogeneous corporate information resources. Carnot executes queries in a distributed environment by dispatching autonomous computing agents to remote sites where they access databases and cooperate among themselves to properly merge resulting data into understandable information.The InfoSleuth project will investigate the use of Carnot technology in a more dynamically changing environment, such as the Internet, where new information sources are constantly being added and for which there is no formal control of the registration of new information sources. In this type of en...
A Complexity Analysis of Space%2DBounded Learning Algorithms for the Constraint Satisfaction Problem.
Learning during backtrack search is a space-intensive process that records information (such as additional constraints) in order to avoid redundant work. In this paper, we analyze the effects of polynomial-spacebounded learning on runtime complexity of backtrack search. One space-bounded learning scheme records only those constraints with limited size, and another records arbitrarily large constraints but deletes those that become irrelevant to the portion of the search space being explored. We find that relevance-bounded learning allows better runtime bounds than size-bounded learning on structurally restricted constraint satisfaction problems. Even when restricted to linear space, our relevancebounded learning algorithm has runtime complexity near that of unrestricted (exponential space-consuming) learning schemes.
Processing Queries for First Few Answers.
Special support for quickly finding the first-few answers of a query is already appearing in commercial database systems. This support is useful in active databases, when dealing with potentially unmanageable query results, and as a declarative alternative to navigational techniques. In this paper, we discuss query processing techniques for first-answer queries. We provide a method for predicting the cost of a first-answer query plan under an execution model that attempts to reduce wasted effort in join pipelining. We define new statistics necessary for accurate cost prediction, and discuss techniques for obtaining the statistics through traditional statistical measures (e.g. selectivity) and semantic data properties commonly specified through modern OODB and relational schemas. The proposed techniques also apply to all-answer query processing when optimizing for fast delivery of the initial query results. 1 Introduction Traditional methods for query processing, primarily those based ...
Using CSP Look%2DBack Techniques to Solve Exceptionally Hard SAT Instances.
Abstract. While CNF propositional satisfiability (SAT) is a sub-class of the more general constraint satisfaction problem (CSP), conventional wisdom has it that some well-known CSP look-back techniques-- including backjumping and learning-- are of little use for SAT. We enhance the Tableau SAT algorithm of Crawford and Auton with look-back techniques and evaluate its performance on problems specifically designed to challenge it. The Random 3-SAT problem space has commonly been used to benchmark SAT algorithms because consistently difficult instances can be found near a region known as the phase transition. We modify Random 3-SAT in two ways which make instances even harder. First, we evaluate problems with structural regularities and find that CSP look-back techniques offer little advantage. Second, we evaluate problems in which a hard unsatisfiable instance of medium size is embedded in a larger instance, and we find the look-back enhancements to be indispensable. Without them, most instances are “exceptionally hard ”-orders of magnitude harder than typical Random 3-SAT instances with the same surface characteristics.
On the Space%2DTime Trade%2Doff in Solving Constraint Satisfaction Problems.
A common technique for bounding the runtime required to solve a constraint satisfaction problem is to exploit the structure of the problem’s constraint graph [Dechter, 92]. We show that a simple structure-based technique with a minimal space requirement, pseudo-tree search [Freuder &amp; Quinn, 85], is capable of bounding runtime almost as effectively as the best exponential space-consuming schemes. Specifically, if we let n denote the number of variables in the problem, w * denote the exponent in the complexity function of the best structure-based techniques, and h denote the exponent from pseudo-tree search, we show h ≤  ( w * + 1) ( lg() n + 1)
A New Approach to Modularity in Rule%2DBased Programming.
In this paper we describe a purely declarative method for introducing modularity into forwardchaining, rule-based languages and its embodiment in the Venus rule language. The method is enforced by the syntax of the language and includes the ability to parameterize the rule groups. Drawing from two of three Venus applications developed to date, we illustrate how this form of modularity contributes directly to the resolution of certain software engineering problems associated with rule languages. 1 Introduction  It is well established that flat monolithic systems, both procedural and rule-based, lead to difficult application development and even more difficult longterm maintenance[17, 13]. The problem is more vexing in rule-based environments since the scope of free variables in a rule&#039;s predicate encompasses the entire working memory. Thus, side-effects of program updates are not limited to the section of code containing the update. In this paper we describe a declarative method for int...
An Optimal Backtrack Algorithm for Tree%2DStructured Constraint Satisfaction problems.

